iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 30
0
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 30

[LeetCode with JavaScript] Day 30: Reverse Linked List

  • 分享至 

  • xImage
  •  

觀前提醒:

  1. 我預設大家已經先思考並分析過題目,沒啥想法才開始 google 找解題靈感。若無,建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法
  2. 承上,既然已經有思考過了,那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了,那我可能解題想法 & 心得的部分就不會寫太多,免得干擾你的思考。
  3. 所有解法都是已經取得系統的 Accepted,但或許不是最優解法,請多包涵。
  4. 最後,歡迎在下面留言指教~教學相長才會進步歐~/images/emoticon/emoticon41.gif

題目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解題想法

要解決這題目,我們採取兩大步驟來處理:

  1. 先宣告三個變數:prevNode、currNode、nextNode。
  2. 然後採取 iterative / Iteration (疊代)的方式來處理。
    2-1. 依順序更改三個 Node 的 pointer,從原本的 prevNode -> currNode -> nextNode。改成 prevNode <- currNode <- nextNode。即可達到我們的目標。

以下舉例為 1->2->3->4->NULL 來說明:
Imgur
Imgur
Imgur
Imgur
Imgur
Imgur
Imgur


以此類推,當 Iteration 跑到最後一步時的情況。
Imgur

CODE

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prevNode = null;
  let currNode = head;
  while (currNode !== null) {
    let nextNode = currNode.next;
    currNode.next = prevNode;
    prevNode = currNode;
    currNode = nextNode;
  }
  return prevNode;
};

心得

或許有人會好奇說,那一開始的 prevNode = currNode 時,那個 currNode 的值還在不在? 答案是存在的,小弟在作圖時,主要是想表達兩個變數之間的關係,便把 currNode 省略不畫。同理,currNode = nextNode 中,nextNode 的圖也沒畫出來,但它也是存在的。

補充:若採取這樣的方式答題,最後一定要回傳 prevNode,詳情請參考下圖:
Imgur
當 while 迴圈跳開後,整個 Linked List 就會長成這樣,所以一定要回傳 prevNode,才能代表整包新的 Linked List 已經被 Reverse 完畢。


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 29: Merge Two Sorted Lists
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言